Chinese Remainder Theorem

The Chinese remainder theorem is a statement about existence of solutions to a system of linear congruences. The problem originates from the book third century book Sun-tzu Suan-ching:

There are certain things whose number is unknown. If we count them by threes, we have two left over; by fives, we have three left over; and by sevens, two are left over. How many things are there?

The theorem is as follows:

Theorem

Given moduli $m_{1}, m_{2}, \dots, m_{n}$ which are pairwise coprime integers, and $a_{1}, a_{2}, \dots, a_{n} \in Z$ , there is a unique solution modulo $m = m_{1} m_{2} \dots m_{n}$ to the system of equations:

\begin{aligned} x & \equiv a_{1} (\mod m_{1}) \\ x & \equiv a_{2} (\mod m_{2}) \\ ⋮ \\ x & \equiv a_{n} (\mod m_{n}) \end{aligned}

Note that the proof given below is non-constructive. For actually finding such a solution, see the chinese remainder theorem algorithm.

The core part of the result that needs to be proven is the following isomorphism of additive groups:

Z / n Z = Z / s Z \oplus Z / t Z

if $gcd (s, t) = 1$ .

The full result then follows by induction.

This is equivalent to the decomposition of cyclic groups. It is proven here again to show the explicit isomorphism from $Z / n Z$ to $Z / s Z \oplus Z / t Z$ , however the proof is otherwise identical, and is only repeated for convenience.

Note that this method does not give an explicit way to invert this isomorphism (that is what the chinese remainder theorem algorithm) is for.

Proof

Consider the homomorphism

ϕ : Z / n Z \to Z / s Z \oplus Z / t Z

given by

ϕ : a + n Z \mapsto (a + s Z, a + t Z) .

We will prove that this is an isomorphism simply by showing that the kernel is just the identity.

\begin{aligned} \ker (ϕ) & = {a + n Z \in Z / n Z : ϕ (a + n Z) = (0 + s Z, 0 + t Z)} \\ = {a + n Z \in Z / n Z : (a + s Z, a + t Z) = (0 + s Z, 0 + t Z)} \\ = {a + n Z \in Z / n Z : a + s Z = 0 + s Z and a + t Z = 0 + t Z} \\ = {a + n Z \in Z / n Z : a \in s Z and a \in t Z} \\ = {a + n Z \in Z / n Z : s ∣ a and t ∣ a} \\ (1) & = {a + n Z \in Z / n Z : s t ∣ a} \\ = {a + n Z \in Z / n Z : n ∣ a} \\ = {0 + n Z} \end{aligned}

where step (1) is where the coprimality condition is used.